package algorithm.leetcode.I401to600;

/**
 * A 次数严格少于2次
 * L 不存在连续的三个或三个以上
 * 未完成
 */


public class Q552 {

    int count = 0;

    public int checkRecord(int n) {
        if (n == 1) return 3;

        int hasLL = 0, hasLS = 0, hasSL = 0, hasSS = 1;
        int noLL = 0, noLP = 1, noPL = 1, noPP = 0;

        int total;
        int MOD = (int) Math.pow(10, 9)+7;

        for (int i = 2; i <= n; i++) {
            int tempHasLL = hasLL, tempHasLS = hasLS, tempHasSL = hasSL, tempHasSS = hasSS;
            int tempNoLL = noLL, tempNoLP = noLP, tempNoPL = noPL, tempNoPP = noPP;
            noLL = tempNoPL; // 无A(所以不考虑L的话只能是P)末尾LL(noLL,下同)只能由末尾两位是noPL+L
            noPL = (tempNoLP + tempNoPP)%MOD;  // noPL只能是noLP和noPP+L得来
            noLP = (tempNoLL + tempNoPL)%MOD;  // noLP只能是npLL和noPL+P得到
            noPP = (tempNoPP + tempNoLP)%MOD;  // noPP只能是noPP和noLP+P得到
            hasLL = tempHasSL;
            hasSL = tempHasLS + tempHasSS;
            hasLS = ((tempHasLL + tempHasSL)%MOD + (tempNoLL + tempNoPL)%MOD)%MOD;
            hasSS = ((tempHasLS + tempHasSS)%MOD + (tempNoLP + tempNoPP)%MOD)%MOD;
        }

        total = (noLL+noPL+noLP+noPP+hasLL+hasLS+hasSL+hasSS)%MOD;
        return total;
    }


}
